{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Brick Wall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leastBricks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #砖墙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的面前有一堵矩形的、由 <code>n</code> 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。</p>\n",
    "\n",
    "<p>你现在要画一条 <strong>自顶向下 </strong>的、穿过 <strong>最少 </strong>砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。<strong>你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。</strong></p>\n",
    "\n",
    "<p>给你一个二维数组 <code>wall</code> ，该数组包含这堵墙的相关信息。其中，<code>wall[i]</code> 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 <strong>穿过的砖块数量最少</strong> ，并且返回 <strong>穿过的砖块数量</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/24/cutwall-grid.jpg\" style=\"width: 493px; height: 577px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>wall = [[1],[1],[1]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    " \n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == wall.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= wall[i].length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= sum(wall[i].length) <= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li>对于每一行 <code>i</code> ，<code>sum(wall[i])</code> 是相同的</li>\n",
    "\t<li><code>1 <= wall[i][j] <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [brick-wall](https://leetcode.cn/problems/brick-wall/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [brick-wall](https://leetcode.cn/problems/brick-wall/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]', '[[1],[1],[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        cut = {}\n",
    "        for row in wall:\n",
    "            if len(row) == 1:\n",
    "                continue\n",
    "            tmp = 0\n",
    "            for brick in row[0:-1]:\n",
    "                tmp += brick\n",
    "                cut[tmp] = cut.get(tmp, 0) + 1\n",
    "        if not cut:\n",
    "            return len(wall)\n",
    "        return len(wall) - sorted(cut.items(), key=operator.itemgetter(1))[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import chain, accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        leastBricks(): Brute Force\n",
    "        1. use a hash table to record every seperate position in each row\n",
    "        2. check each line to get the result, use a flag to sign whether a position have been counted\n",
    "        3. return the least bricks\n",
    "        \"\"\"\n",
    "        row = len(wall)\n",
    "        if row == 1:\n",
    "            return int(len(wall[0]) == 1)\n",
    "        P_cnt = collections.Counter(chain.from_iterable(map(accumulate, wall)))\n",
    "        return row if len(P_cnt) == 1 else row - P_cnt.most_common(2)[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count={}\n",
    "        for row in wall:\n",
    "            row2=self.comb(row)\n",
    "            for r in row2:\n",
    "                try:\n",
    "                    count[r]+=1\n",
    "                except:\n",
    "                    count[r]=1\n",
    "        count=list(sorted(count.values()))\n",
    "        try:\n",
    "            return len(wall)-count[-2]\n",
    "        except:\n",
    "            return len(wall)\n",
    "    def comb(self,data):\n",
    "        result=[data[0]]\n",
    "        for d in data[1:]:\n",
    "            result.append(d+result[-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        gap = {}\n",
    "        for row in wall:\n",
    "            width = 0\n",
    "            for i in range(len(row) - 1):\n",
    "                length = row[i]\n",
    "                width += length\n",
    "                if width in gap:\n",
    "                    gap[width] += 1\n",
    "                else:\n",
    "                    gap[width] = 1\n",
    "        if len(gap):\n",
    "            return len(wall) - max(gap.values())\n",
    "        else:\n",
    "            return len(wall)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        d={}\n",
    "        \n",
    "        for r in wall:\n",
    "            if len(r)>1:\n",
    "                t=0\n",
    "                for c in r[:-1]:\n",
    "                    t+=c\n",
    "                    try:\n",
    "                        d[t]+=1\n",
    "                    except KeyError:\n",
    "                        d[t]=1\n",
    "        return len(wall)-max(list(d.values())+[0])\n",
    "    \n",
    "        \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "#       记录每个位置不被穿过的次数\n",
    "        a={}\n",
    "        n=len(wall)\n",
    "        for i in range(n):\n",
    "            now=0\n",
    "            for j in range(len(wall[i])):\n",
    "                # print(wall[i][j])\n",
    "                now+=wall[i][j]\n",
    "                a.setdefault(now,0)\n",
    "                a[now]+=1\n",
    "        # print(a)\n",
    "        a.pop(max(a))\n",
    "        if len(a)==0:\n",
    "            return n\n",
    "        return n-max([a[x] for x in a])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        width = {0:0}\n",
    "        for floor in wall:\n",
    "            s = 0\n",
    "            for n in floor[:-1]:\n",
    "                s += n\n",
    "                width[s] = width.get(s, 0) + 1\n",
    "        return len(wall) - max(width.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        # 超出时间限制\n",
    "        from collections import Counter\n",
    "        mycount = Counter()\n",
    "        for x in wall:\n",
    "            tmp = [sum(x[:i]) for i in range(1, len(x)+1)]\n",
    "            mycount += Counter(tmp)\n",
    "        #print(mycount)\n",
    "        # 去掉右边界\n",
    "        mycount[sum(x)] = 0\n",
    "        return len(wall) - max(mycount.values())\n",
    "        \"\"\"\n",
    "        mydict = dict()\n",
    "        for x in wall:\n",
    "            tmp = [sum(x[:i]) for i in range(1, len(x)+1)]\n",
    "            for y in tmp:\n",
    "                mydict[y] = mydict.get(y, 0) + 1\n",
    "        mydict[sum(x)] = 0\n",
    "        return len(wall) - max(mydict.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not wall: return 0\n",
    "        brickRecord = {}\n",
    "        \n",
    "        for i in range(len(wall)):\n",
    "            start = 0\n",
    "            # print(brickRecord)\n",
    "            for j in range(len(wall[i]) - 1):\n",
    "                index = start + wall[i][j]\n",
    "                if index in brickRecord.keys():\n",
    "                    brickRecord[index] -= 1\n",
    "                else:\n",
    "                    brickRecord[index] = len(wall) - 1\n",
    "                start += wall[i][j]\n",
    "        # print(brickRecord)\n",
    "        if not brickRecord: return len(wall)\n",
    "        else:\n",
    "            orderbrickRecord = sorted(brickRecord.items(), key = lambda item:item[1])\n",
    "            return orderbrickRecord[0][1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall):\n",
    "        \"\"\"\n",
    "        :type wall: List[List[int]]\n",
    "        :rtype: int\n",
    "        leastBricks(): Brute Force\n",
    "        1. use a hash table to record every seperate position in each row\n",
    "        2. check each line to get the result, use a flag to sign whether a position have been counted\n",
    "        3. return the least bricks\n",
    "        \"\"\"\n",
    "        row = len(wall)\n",
    "        if row == 1:\n",
    "            return int(len(wall[0]) == 1)\n",
    "        P = []\n",
    "        for i in range(row):\n",
    "            P.append(itertools.accumulate(wall[i]))\n",
    "        P = itertools.chain.from_iterable(P)\n",
    "        P_cnt = collections.Counter(P)\n",
    "        return row if len(P_cnt) == 1 else row - P_cnt.most_common(2)[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        # 用一个Hash记录在每一个纵坐标上有多少个砖块\n",
    "        # 怎么确定一块砖是在一个间歇中的 --> 压在叠加的数字上的就是砖的间隙了\n",
    "        # 砖的行数可以是不等的\n",
    "        # 上面的解答会打爆内存\n",
    "\n",
    "        # 一共有m层砖，最多的数量为m层\n",
    "        # 我们看看除了墙的两端，哪些位置会空出一条缝隙，就在该位置上减少一层砖\n",
    "        # 最后再统计就好了\n",
    "        from collections import defaultdict\n",
    "        length = sum(wall[0])\n",
    "        m = len(wall)\n",
    "        brick_on_lines = defaultdict(lambda: m)\n",
    "        for i in range(m):\n",
    "            presum = 0\n",
    "            for brick in wall[i][:-1]:      # 找出一层墙中的缝隙\n",
    "                presum += brick\n",
    "                brick_on_lines[presum] -= 1\n",
    "        least_value = m\n",
    "        for key, value in brick_on_lines.items():\n",
    "            least_value = min(value, least_value)\n",
    "        return least_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import sys\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        lm = {}\n",
    "        for line in wall:\n",
    "            lth = 0\n",
    "            for x in line[0:-1]:\n",
    "                lth+=x\n",
    "                if lth in lm:\n",
    "                    lm[lth] += 1\n",
    "                else:\n",
    "                    lm[lth] =1\n",
    "        res = 0\n",
    "        for i in lm.keys():\n",
    "            if lm[i] > res:\n",
    "                res = lm[i]\n",
    "        return len(wall) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        res, n = [], len(wall)\n",
    "        for tmp_wall in wall:\n",
    "            if len(tmp_wall) == 1:\n",
    "                continue\n",
    "            sum = 0\n",
    "            for i in range(len(tmp_wall)-1):\n",
    "                if i == 0:\n",
    "                    sum = tmp_wall[i]\n",
    "                else:\n",
    "                    sum+=tmp_wall[i]\n",
    "                res.append(sum)\n",
    "        dic = dict(Counter(res))\n",
    "        ans = len(wall)\n",
    "        for i in dic:\n",
    "            ans = min(ans, n-dic[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        bricks = {}\n",
    "        for i in wall:\n",
    "            t = 0\n",
    "            for j in range(len(i) - 1):\n",
    "                t = t + i[j]\n",
    "                bricks[t] = bricks.get(t, 0) + 1\n",
    "        res = 0\n",
    "        for i in bricks.keys():\n",
    "            res = max(res, bricks[i])\n",
    "        return len(wall) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 面前有一堵方形的, 由多行砖块组成的砖墙. 这些砖块高度相同但是宽度不同. 现在要画一条自顶向下的, 穿过最少砖块的垂线.\n",
    "# 返回穿过的砖块数量, 不能沿着墙的两个垂直边缘之一画线\n",
    "# 其实就是累和, 找最多的相同的值\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "\n",
    "        def helper(block: List[int]):\n",
    "            # 不用统计最后一位, 因为最后一位都一样\n",
    "            len_block = len(block)\n",
    "            res = [0 for i in range(len_block-1)]\n",
    "            for i in range(len_block-1):\n",
    "                if i == 0:\n",
    "                    res[i] = block[i]\n",
    "                else:\n",
    "                    res[i] = res[i-1] + block[i]\n",
    "            return res\n",
    "\n",
    "        if not wall:\n",
    "            return 0\n",
    "\n",
    "        len_wall = len(wall)\n",
    "        len_block = len(wall[0])\n",
    "        for i in range(len_wall):\n",
    "            wall[i] = helper(wall[i])\n",
    "        \n",
    "        tmp = []\n",
    "        for i in range(len_wall):\n",
    "            tmp += wall[i]\n",
    "        \n",
    "        counter = Counter(tmp)\n",
    "        tmp = [item[1] for item in counter.items()]\n",
    "        if not tmp:\n",
    "            return len_wall\n",
    "        return len_wall - max(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        n = len(wall)\n",
    "        board = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            # 遍历找每一行砖块的边缘的位置\n",
    "            pos = 0\n",
    "            for j in range(len(wall[i])-1):\n",
    "                # pos是当前砖块边缘的位置\n",
    "                pos += wall[i][j]\n",
    "                board[pos] += 1\n",
    "        if not board:\n",
    "            return n\n",
    "        return n-max(board.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        hashmap = dict()\n",
    "        for row in wall:\n",
    "            a = 0\n",
    "            for brick in row[:-1]:\n",
    "                a += brick\n",
    "                hashmap[a] = hashmap.get(a,0) +1\n",
    "        return len(wall) - max(hashmap.values(),default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        from collections import Counter\n",
    "        n = len(wall)\n",
    "        width = len(wall[0])\n",
    "        c = Counter()\n",
    "\n",
    "        for w in wall:\n",
    "            m = 0\n",
    "            for i in w[:-1]:\n",
    "                m += i\n",
    "                c[m] += 1\n",
    "        \n",
    "        if len(c) != 0:\n",
    "            _, counts = c.most_common(1)[0]\n",
    "        else:\n",
    "            counts = 0\n",
    "        \n",
    "        return n - counts\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        m = len(wall)\n",
    "        res = [0]\n",
    "        for i in range(m):\n",
    "            if len(wall[i]) == 1:\n",
    "                continue\n",
    "            sumn = wall[i][0]\n",
    "            res.append(sumn)\n",
    "            for j in range(1, len(wall[i])-1):\n",
    "                sumn += wall[i][j]\n",
    "                res.append(sumn)\n",
    "        a = res.count(max(res,key=res.count))\n",
    "        if res == [0]:\n",
    "            return m\n",
    "        else:\n",
    "            return m - a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        max_len = sum(wall[0])\n",
    "        heigh = len(wall)\n",
    "        ans = heigh\n",
    "        posb = []\n",
    "        for i in range(heigh):\n",
    "            if wall[i][0] != max_len and wall[i][0] not in posb:\n",
    "                posb.append(wall[i][0])\n",
    "            for j in range(1,len(wall[i])):\n",
    "                wall[i][j] += wall[i][j-1]\n",
    "                if wall[i][j] != max_len and wall[i][j] not in posb:\n",
    "                    posb.append(wall[i][j])\n",
    "        \n",
    "        for i in posb:\n",
    "            temp_ans = heigh\n",
    "            for j in range(heigh):\n",
    "                #print(i, wall[j])\n",
    "                if i in wall[j]:\n",
    "                    temp_ans -= 1\n",
    "            ans = min(ans, temp_ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        n = len(wall)\n",
    "        ls = []\n",
    "        for i in range(n):\n",
    "            wall[i] = list(accumulate(wall[i]))[:-1]\n",
    "            for j in range(len(wall[i])):\n",
    "                ls.append(wall[i][j])\n",
    "        count = Counter(ls)\n",
    "        temp = sorted(count, key = lambda x:count[x], reverse = True)\n",
    "        return n - count[temp[0]] if temp else n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        length = sum(wall[0])\n",
    "        print(length)\n",
    "        n = len(wall)\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(int)\n",
    "        for w in wall:\n",
    "            wid = 0\n",
    "            for d in w:\n",
    "                wid += d\n",
    "                if wid!=length:\n",
    "                    dic[wid]+=1\n",
    "        return n-max(dic.values()) if len(dic)>0 else n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        dic={}\n",
    "        for li in wall:\n",
    "            if len(li)>1:\n",
    "                for i in range(0,len(li)-1):\n",
    "                    li[i+1]=li[i]+li[i+1]\n",
    "                    if li[i] not in dic.keys():\n",
    "                        dic[li[i]]=0\n",
    "                    dic[li[i]]+=1\n",
    "        \n",
    "        k=sorted(dic.keys())\n",
    "        res=0\n",
    "        for z in k:\n",
    "            res=max(res,dic[z])\n",
    "        return len(wall)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        # 统计所有块的起点和终点，因为线一定是穿过某些块的边界\n",
    "        hashmap = {}\n",
    "        max_len = sum(wall[0])\n",
    "        max_boarder_num = 0\n",
    "        for w_list in wall:\n",
    "            start = 0\n",
    "            for w in w_list:\n",
    "                end = start + w\n",
    "                if 0 < end < max_len:\n",
    "                    if end in hashmap:\n",
    "                        hashmap[end] += 1\n",
    "                    else:\n",
    "                        hashmap[end] = 1\n",
    "                    \n",
    "                    max_boarder_num = max(max_boarder_num, hashmap[end])\n",
    "                    start = end\n",
    "        return len(wall) - max_boarder_num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        n = len(wall)\n",
    "        for row in wall:\n",
    "            presum = 0\n",
    "            # 每一行最后1列不列入计算，否则会把最右侧垂直线考虑进去\n",
    "            for i in range(len(row) - 1):\n",
    "                # 计算每一行砖的宽度和\n",
    "                presum += row[i]\n",
    "                # 如果有相同的前缀和，这里会+1\n",
    "                dic[presum] += 1\n",
    "        # 总高度 减去 前缀和数量最多的值\n",
    "        return n - max(dic.values(), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        n = len(wall)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            weight = 0\n",
    "            for j in range(len(wall[i]) - 1):\n",
    "                weight += wall[i][j]\n",
    "                if weight in dic:\n",
    "                    dic[weight] += 1\n",
    "                else:\n",
    "                    dic[weight] = 1\n",
    "        if len(dic) == 0:\n",
    "            return n\n",
    "        return n - max(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "\n",
    "        prefixSum = defaultdict(int)\n",
    "\n",
    "        n = len(wall)\n",
    "        for i in range(0, n):\n",
    "\n",
    "            currSum = 0\n",
    "            # 每一行砖的最后一列不要计算进来, 否则会把最右侧的垂直线考虑进去\n",
    "            for j in range(0, len(wall[i]) - 1):\n",
    "                # 计算每一行的砖的宽度和\n",
    "                currSum += wall[i][j]\n",
    "                # 如果有相同的前缀和, 这里会+1\n",
    "                prefixSum[currSum] += 1\n",
    "        # 总高度 减去 前缀和数量最多的\n",
    "        return n - max(prefixSum.values(), default=0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        height = len(wall)\n",
    "        dict1 = {}\n",
    "        for i in wall:\n",
    "            temp_sum = 0 # 用前缀和表示砖缝\n",
    "            for j in i[:-1]: # 不包含最后一块砖\n",
    "                temp_sum += j\n",
    "                dict1[temp_sum] = dict1.setdefault(temp_sum, 0) + 1\n",
    "        max_space = max(dict1.values()) if dict1 else 0         # 前缀和最大表示砖块在该处缝隙最大（缝隙长度）\n",
    "        return height - max_space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import sortedlist \n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        hashmap = collections.defaultdict(int)\n",
    "        for i in wall:\n",
    "            cur_sum = 0\n",
    "            for j in range(len(i)-1):\n",
    "                cur_sum += i[j]\n",
    "                hashmap[cur_sum] += 1\n",
    "        # print(hashmap)\n",
    "        return len(wall)-max(hashmap.values(),default=0)\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
